# -*- coding=utf-8 -*-
# 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可
# 数字 1-9 在每一行只能出现一次
# 数字 1-9 在每一列只能出现一次
# 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次
# 数独部分空格内已填入了数字，空白格用 '.' 表示

# 示例 1:
# 输入:
# [
#   ["5","3",".",".","7",".",".",".","."],
#   ["6",".",".","1","9","5",".",".","."],
#   [".","9","8",".",".",".",".","6","."],
#   ["8",".",".",".","6",".",".",".","3"],
#   ["4",".",".","8",".","3",".",".","1"],
#   ["7",".",".",".","2",".",".",".","6"],
#   [".","6",".",".",".",".","2","8","."],
#   [".",".",".","4","1","9",".",".","5"],
#   [".",".",".",".","8",".",".","7","9"]
# ]
# 输出: true

# 示例 2:
# 输入:
# [
#   ["8","3",".",".","7",".",".",".","."],
#   ["6",".",".","1","9","5",".",".","."],
#   [".","9","8",".",".",".",".","6","."],
#   ["8",".",".",".","6",".",".",".","3"],
#   ["4",".",".","8",".","3",".",".","1"],
#   ["7",".",".",".","2",".",".",".","6"],
#   [".","6",".",".",".",".","2","8","."],
#   [".",".",".","4","1","9",".",".","5"],
#   [".",".",".",".","8",".",".","7","9"]
# ]
# 输出: false

# 解释: 除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同
#      但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的

# 说明:
# 一个有效的数独（部分已被填充）不一定是可解的
# 只需要根据以上规则，验证已经填入的数字是否有效即可
# 给定数独序列只包含数字 1-9 和字符 '.'
# 给定数独永远是 9x9 形式的

# import re;

# class Solution(object):
#     def isValidSudoku(self, board):
#         """
#         :type board: List[List[str]]
#         :rtype: bool
#         """
#         for line in board:
#             if self.isRepate(line):
#                 return False;

#         for i in range(len(board)):
#             col = [line[i] for line in board];
#             if self.isRepate(col):
#                 return False;

#         for i in range(3):
#             for j in range(3):
#                 row = i * 3;
#                 col = j * 3;

#                 square = "";
#                 for k in range(3):
#                     square += "".join(board[row + k][col : col + 3]);

#                 if self.isRepate(square):
#                     return False;

#         return True;

#     def isRepate(self, line):
#         s_line = "";
#         for c in line:
#             if c == ".":
#                 continue;
#             s_line = s_line + c;
#         return re.search(re.compile(r"(\d).*(\1)"), s_line) != None;





# 阅读官方的解决方案，一遍遍历
class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        z_row = [{} for i in range(9)];
        z_col = [{} for i in range(9)];
        z_box = [{} for i in range(9)];
        for row in range(9):
            for col in range(9):
                if board[row][col] == ".":
                    continue;

                box_index = (row / 3) * 3 + col / 3;
                value = board[row][col];
                z_row[row][value] = z_row[row].get(value, 0) + 1;
                z_col[col][value] = z_col[col].get(value, 0) + 1;
                z_box[box_index][value] = z_box[box_index].get(value, 0) + 1;
                if z_row[row][value] > 1 or z_col[col][value] > 1 or z_box[box_index][value] > 1:
                    return False;
        return True;


t = Solution();
print t.isValidSudoku(
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]);